package com.gitee.feizns.explore.data_structure.linked_list.singly.sortedListToBST;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author feizns
 * @since 2020/3/5
 */
public class SortedListToBST {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(distributeCandies(7, 4)));
    }

    List<ListNode> list = new ArrayList<>();

    public TreeNode sortedListToBST(ListNode head) {
        for (ListNode tmp = head; tmp != null; tmp = tmp.next)
            list.add(tmp);
        return buildTree(0, list.size() - 1);
    }

    private TreeNode buildTree(int l, int r) {
        if ( l > r )
            return null;
        int mid = (l + r) / 2;
        TreeNode ret = new TreeNode(list.get(mid).val);
        ret.left = buildTree(l, mid - 1);
        ret.right = buildTree(mid + 1, r);
        return ret;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static int[] distributeCandies(int candies, int num_people) {
        int[] ret = new int[num_people];
        int n = 1;
        int i = 0;
        while( candies > 0 ) {
            n = candies > n ? n : candies;
            candies -= n;
            ret[i++] += n++;
            if ( i == ret.length )
                i = 0;
        }
        return ret;
    }

}
